package com.nep.NEPG.datastructure;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Consumer;

public class BinarySearchTree<T> implements Serializable {
     private Node<T> root;
     private final Comparator<T> comparator;

     private static class Node<T> implements Serializable {
          T data;
          Node<T> left;
          Node<T> right;

          Node(T data) {
               this.data = data;
               this.left = null;
               this.right = null;
          }
     }

     public BinarySearchTree(Comparator<T> comparator) {
          this.root = null;
          this.comparator = comparator;
     }

     public void insert(T data) {
          root = insertRec(root, data);
     }

     private Node<T> insertRec(Node<T> root, T data) {
          if (root == null) {
               return new Node<>(data);
          }

          if (comparator.compare(data, root.data) < 0) {
               root.left = insertRec(root.left, data);
          } else if (comparator.compare(data, root.data) > 0) {
               root.right = insertRec(root.right, data);
          }

          return root;
     }

     public boolean contains(T data) {
          return containsRec(root, data);
     }

     private boolean containsRec(Node<T> root, T data) {
          if (root == null) {
               return false;
          }

          if (comparator.compare(data, root.data) == 0) {
               return true;
          }

          return comparator.compare(data, root.data) < 0
                    ? containsRec(root.left, data)
                    : containsRec(root.right, data);
     }

     public T search(T key) {
          return searchRec(root, key);
     }

     private T searchRec(Node<T> root, T key) {
          if (root == null) {
               return null;
          }

          if (comparator.compare(key, root.data) == 0) {
               return root.data;
          }

          return comparator.compare(key, root.data) < 0
                    ? searchRec(root.left, key)
                    : searchRec(root.right, key);
     }

     public void delete(T data) {
          root = deleteRec(root, data);
     }

     private Node<T> deleteRec(Node<T> root, T data) {
          if (root == null) {
               return null;
          }

          if (comparator.compare(data, root.data) < 0) {
               root.left = deleteRec(root.left, data);
          } else if (comparator.compare(data, root.data) > 0) {
               root.right = deleteRec(root.right, data);
          } else {
               // Node with only one child or no child
               if (root.left == null) {
                    return root.right;
               } else if (root.right == null) {
                    return root.left;
               }

               // Node with two children: Get the inorder successor (smallest in the right
               // subtree)
               root.data = minValue(root.right);

               // Delete the inorder successor
               root.right = deleteRec(root.right, root.data);
          }

          return root;
     }

     private T minValue(Node<T> root) {
          T minv = root.data;
          while (root.left != null) {
               minv = root.left.data;
               root = root.left;
          }
          return minv;
     }

     public void inorderTraversal(Consumer<T> consumer) {
          inorderRec(root, consumer);
     }

     private void inorderRec(Node<T> root, Consumer<T> consumer) {
          if (root != null) {
               inorderRec(root.left, consumer);
               consumer.accept(root.data);
               inorderRec(root.right, consumer);
          }
     }

     public List<T> toList() {
          List<T> result = new ArrayList<>();
          inorderTraversal(result::add);
          return result;
     }

     public boolean isEmpty() {
          return root == null;
     }

     public void clear() {
          root = null;
     }
}